package org.agile4j.math.permutation;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 排列实现 田忌赛马
 *
 * @author hanyx
 * @date 2019/01/04
 */
public class PermutationDemo {

    /**
     * 设置田忌的马跑完需要时间
     */
    public static Map<String, Double> tHorsesTime = new HashMap<>();

    /**
     * 设置齐王的马跑完需要时间
     */
    public static Map<String, Double> qHorsesTime = new HashMap<>();

    public static ArrayList<String> qHorses = new ArrayList<>();

    static {
        tHorsesTime.put("t1", 1.5);
        tHorsesTime.put("t2", 2.5);
        tHorsesTime.put("t3", 3.5);

        qHorsesTime.put("q1", 1.0);
        qHorsesTime.put("q2", 2.0);
        qHorsesTime.put("q3", 3.0);

        qHorses.add("q1");
        qHorses.add("q2");
        qHorses.add("q3");
    }

    /**
     * 使用递归,找出所有可能的马匹出战顺序
     *
     * @param horses 目前剩余没出战的马匹
     * @param result 当前已出战的马匹及顺序
     */
    public static void permutate(ArrayList<String> horses, ArrayList<String> result) {
        // 所有马匹都已出战, 判断获胜方,输出结果
        if (horses.size() == 0) {
            System.out.println(result);
            compare(result, qHorses);
            return;
        }

        for (String horse : horses) {
            // 剩下未出战的马匹中,选择一匹,加入结果
            ArrayList<String> newResult = (ArrayList<String>) result.clone();
            newResult.add(horse);

            // 将已选择的马匹从未出战的列表中移除
            ArrayList<String> restHorese = (ArrayList<String>) horses.clone();
            restHorese.remove(horse);

            // 递归调用,对剩余的马匹继续排列
            permutate(restHorese, newResult);
        }
    }

    /**
     * 比较谁快
     *
     * @param tHorses 田忌的马
     * @param qHorses 齐王的马
     */
    public static void compare(ArrayList<String> tHorses, ArrayList<String> qHorses) {
        int tWinCount = 0;
        for (int i = 0; i < tHorses.size(); i++) {
            System.out.println(tHorsesTime.get(tHorses.get(i)) + "\t" + qHorsesTime.get(qHorses.get(i)));
            if (tHorsesTime.get(tHorses.get(i)) < qHorsesTime.get(qHorses.get(i))) {
                tWinCount++;
            }
        }
        if (tWinCount > tHorses.size() / 2) {
            System.out.println("田忌获胜");
        } else {
            System.out.println("齐王获胜");
        }
    }

    public static void main(String[] args) {
        ArrayList<String> tHorses = new ArrayList<>(Arrays.asList("t1", "t2", "t3"));
        permutate(tHorses, new ArrayList<>());
    }
}
